Given a Galois connection we can compose the left and right maps to get a closure operator
A closure operator \(P \xrightarrow{j} P\) on a preorder \(P\)
A monotone map such that for all \(p \in P\) we have:
\(p \leq j(p)\)
\(j(j(p)) \cong j(p)\)
Example of a closure operator
Think of the preorder of arithmatic expressions such as \(12, 4+2+4, 9*(2+3)\), where the \(\leq\) operators denotes whether an expression can be simplified to another.
A computer program \(j\) that evaluates expressions is a monotonic function on the preorder to itself (if you can reduce x to y, then \(j(x)\) should be able to be rewritten as \(j(y)\).
The requirements of closure operator say that \(j\) should be a simplification, and that trying to reduce an expression which has already been reduced will do nothing further.
Just as adjunctions give rise to closure operators, from every closure operator we may construct an adjunction.
Let \(P \xrightarrow{j} P\) be a closure operator.
Get a new preorder by looking at a subset of \(P\) fixed by \(j\).
\(fix_j\) defined as \(\{p \in P\ |\ j(p)\cong p\}\)
Define a left adjoint \(P \xrightarrow{j} fix_j\) and right adjoint \(fix_j \xhookrightarrow{g} P\) as simply the inclusion function.
To see that \(j \dashv g\), we need to verify \(j(p) \leq q \iff p \leq q\)
Show \(\rightarrow\):
Because \(j\) is a closure operator, \(p \leq j(p)\)
\(j(p) \leq q\) implies \(p \leq q\) by transivity.
Show \(\leftarrow\):
By monotonicity of \(j\) we have \(p \leq q\) implying \(j(p) \leq j(q)\)
\(q\) is a fix point, so the RHS is congruent to \(q\), giving \(j(p) \leq q\).
Examples of closure operators from logic.
Take set of all propositions as a preorder, where \(p \leq q\) iff \(p\) implies \(q\).
Some modal operators are closure operators
E.g. \(j(p)\) means “Assuming Bob is in Chicago, p”
\(p \implies j(p)\) (the logic is monotonic, adding assumptions does not make something true into something false.
\(j(j(p)) = j(p)\) (the assumption is idempotent)
Given \(f \dashv g\), prove that the composition of left and right adjoint monotone maps is a closure operator
Show \(p \leq (f;g)(p)\)
Show \((f;g;f;g)(p) \cong (f;g)(p)\)
This is one of the conditions of adjoint functors: \(p \leq g(f(p))\)
The \(\leq\) direction is an extension of the above: \(p \leq g(f(p)) \leq g(f(g(f(p))))\)
Galois property: \(q \geq f(g(q))\), substitute \(f(p)\) for \(q\) to get \(f(p) \geq f(g(f(p)))\).
Because \(g\) is a monotone map, we can apply it to both sides to get \(g(f(p)) \geq g(f(g(f(p))))\)